import java.util.*;
/**
 * @author Diego Yon 10070
 * Algoritmos y Estructura de Datos
 * Hoja de Trabajo 7
 */
public class Driver {
	/**
	 * Metodo main donde empieza la ejecucion del programa.
	 * @param args
	 */
	public static void main(String args[]){
		// read System.in one character at a time
		Scanner s = new Scanner(System.in).useDelimiter("");
		System.out.print("Ingrese cadena: ");
		s.nextLine();
		List<node> freq = new SinglyLinkedList<node>();
		
		// read data from input
		while (s.hasNext()){
			// s.next() returns string; we're interested in first char
			char c = s.next().charAt(0);
			// look up character in frequency list
			node query = new node(c);
			
			/*node item = freq.remove(query);
			if (item == null){ // not found, add new node
				freq.addFirst(query);
			} 
			else{ // found, increment node
				item.frequency++;
				freq.addFirst(item);
			}*/
		}
		// insert each character into a Huffman tree
		
		OrderedList<huffmanTree> trees = new OrderedList<huffmanTree>();
		
		for (node n : freq){
			trees.add(new huffmanTree(n));
		}
		// merge trees in pairs until one remains
		Iterator ti = trees.iterator();
		while (trees.size() > 1){
			// construct a new iterator
			ti = trees.iterator();
			// grab two smallest values
			huffmanTree smallest = (huffmanTree)ti.next();
			huffmanTree small = (huffmanTree)ti.next();
			// remove them
			trees.remove(smallest);
			trees.remove(small);
			// add bigger tree containing both
			trees.add(new huffmanTree(smallest,small));
		}
		// print only tree in list
		ti = trees.iterator();
		Assert.condition(ti.hasNext(),"Huffman tree exists.");
		huffmanTree encoding = (huffmanTree)ti.next();
		encoding.print();
	}
}
